﻿// 4558. 奶牛零食.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>


using namespace std;

/*

https://www.acwing.com/problem/content/4561/
一个双端队列中有 N 个整数，依次为 a1,a2,…,aN。

每次弹出操作可以将当前位于队首或队尾的某个元素弹出队列。

每次弹出操作都可以获得一定的分数。

第 i 次弹出操作可以获得的分数为：i×x，其中 x 为弹出的元素值，次数从 1 开始计数。

我们希望通过合理进行弹出操作，获取尽可能多的分数。

请你计算可以获得的最大可能分数。

输入格式
第一行包含整数 N。

接下来 N 行，包含 N 个整数 a1,a2,…,aN。

输出格式
一个整数，表示最大可能分数。

数据范围
1≤N≤2000
,
1≤ai≤1000。

输入样例：
5
1
3
1
5
2
输出样例：
43
样例解释
最佳弹出方案为依次弹出 a1,a5,a2,a3,a4
，获得总分数为 1×1+2×2+3×3+4×1+5×5=43。
*/
const int N = 2010;
int arr[N];
int gl; int gr;

int dp[N][N];

int dfs(int l, int r,int idx) {
	if (l > r) return 0;
	

	if (dp[l][r] != -1)  return dp[l][r];
	int ll = dfs(l + 1, r, idx + 1) + idx * arr[l];
	int rr = dfs(l, r - 1, idx + 1) + idx * arr[r];
	dp[l][r] = max(dp[l][r], ll);
	dp[l][r] = max(dp[l][r], rr);

	return dp[l][r];
}


int main()
{
	cin >> gr; gl = 1;
	for (int i = 1; i <= gr; i++) {
		cin >> arr[i];
	}
	memset(dp, -1, sizeof dp);
	dfs(gl, gr,1);
	cout << dp[gl][gr] << endl;

	return 0;
}

 